#ifdef KITSCHY_DEBUG_MEMORY 
#include "debug_memorymanager.h"
#endif

#ifdef WIN32
#include "windows.h"
#else
#include <sys/time.h>
#include <time.h>
#endif
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stdarg.h"
#include "math.h"

#include "BList.h"

#include "symbol.h"
#include "sort.h"
#include "ontology.h"
#include "featureterm.h"
#include "FTKBase.h"
#include "AUfeatureterm.h"
#include "FT_refinement.h"
#include "FT_generalization.h"

#include "psm.h"
#include "rINDUCTION.h"


/*
	
	rINDUCTION2 does not delete the positive examples covered by a rule once it is found. With the expectation of finding
	better rules during the exploration of the remaining search space.

 */


bool rINDUCTIONHypothesis::learn2(List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model)
{
	FeatureTerm *solution;
	List<FeatureTerm> solutions;
	List< List<FeatureTerm> > descriptions;
	List<FeatureTerm> positive;
	List<FeatureTerm> negative;


	/* Compute the different solutions: */ 
	{
		int pos;
		FeatureTerm *c,*s,*d;
		List<FeatureTerm> l,*tmp;

		l.Instance(*cases);
		while(l.Iterate(c)) {
/*
			{
				char *s=c->toStringNOOS(domain_model);
				printf("%s\n",s);
				delete []s;
			}
*/			
			tmp=c->readPath(description_path);
			if (tmp->Length()==1) d=tmp->ExtractIni();
							 else d=0;
			delete tmp;
			tmp=c->readPath(solution_path);
			if (tmp->Length()==1) s=tmp->ExtractIni();
							 else s=0;
			delete tmp;
			
			pos=solutions.Position(s);
			if (pos==-1) {
				solutions.Add(s);
				tmp=new List<FeatureTerm>;
				tmp->Add(d);
				descriptions.Add(tmp);
			} else {
				delete s;
				descriptions[pos]->Add(d);
			} /* if */ 
		} /* while */ 
	}

	/* Compute the default solution: */ 
	{
		int max=-1;
		FeatureTerm *s;
		List<FeatureTerm> *tmp;

		m_default_solution=0;

		solutions.Rewind();
		descriptions.Rewind();

		while(solutions.Iterate(s) &&  descriptions.Iterate(tmp)) {
			if (max==-1 || tmp->Length()>max) {
				max=tmp->Length();
				delete m_default_solution;
				m_default_solution=new FeatureTerm(s);
			} /* if */ 
		} /* while */ 
	}

	solutions.Rewind();
	while(solutions.Iterate(solution)) {
		learn2_single_class(solution,cases,description_path,solution_path,o,domain_model);
	} /* while */ 

	return true;
} /* rINDUCTIONHypothesis::learn2 */ 





bool rINDUCTIONHypothesis::learn2_single_class(FeatureTerm *solution,List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model)
{
	List<FeatureTerm> positive;
	List<FeatureTerm> negative;

	/* Learn a set of patterns for the current solution: */ 
	{
		char *s=solution->toStringNOOS(domain_model);
		printf("\nrINDUCTION2: building model for %s --------------------------------------------------\n\n",s);
		delete []s;
	}

	/* Create the positive and negative examples lists: */ 
	{
		FeatureTerm *c,*s,*d;
		List<FeatureTerm> l,*tmp;

		l.Instance(*cases);
		while(l.Iterate(c)) {
			tmp=c->readPath(description_path);
			if (tmp->Length()==1) d=tmp->ExtractIni();
							 else d=0;
			delete tmp;
			tmp=c->readPath(solution_path);
			if (tmp->Length()==1) s=tmp->ExtractIni();
							 else s=0;
			delete tmp;

			if (solution->equivalents(s)) {
				positive.Add(d);
			} else {
				negative.Add(d);
			} /* if */ 
			delete s;
		} /* while */ 
	}


	if (negative.EmptyP()) {
		FeatureTerm *pattern=new FeatureTerm((Symbol *)0,o->get_sort("any"),0);

		printf("rINDUCTION2: rule found, covers %i positive examples\n",positive.Length());
		{
			char *s1,*s2;
			s1=solution->toStringNOOS(domain_model);
			s2=pattern->toStringNOOS(domain_model);
			printf("rINDUCTION2: rule is for class %s,\n%s\n\n",s1,s2);
			delete []s1;
			delete []s2;
		}
		fflush(0);

		m_patterns.Add(pattern);
		m_solutions.Add(new FeatureTerm(solution));
		m_reliability.Add(new float(1));
		positive.Delete();
		negative.Delete();
	} else {


		/* find the shortest description that covers only positive examples: */ 
		FeatureTerm *description,*d,*refinement,*problem;
		List<FeatureTerm> open_descriptions;
		List<int> open_coverage;
		List<bool> open_positive_coverage;
		List<FeatureTerm> *refinements;
		bool valid,is_solution,*positive_coverage;
		int i;

		printf("rINDUCTION2: %i positive, %i negative\n",positive.Length(),negative.Length());
		fflush(0);
		open_descriptions.Add(new FeatureTerm((Symbol *)0,o->get_sort("any"),0));
		open_coverage.Add(new int(positive.Length()));

		positive_coverage=new bool[positive.Length()];
		for(i=0;i<positive.Length();i++) positive_coverage[i]=true;
		open_positive_coverage.Add(positive_coverage);

		do{
			bool new_pattern=false;

//				printf("%i\n",open_descriptions.Length());

//				SELECTION METHOD 0: simply the first
/*
			description=open_descriptions.ExtractIni();
			delete open_coverage.ExtractIni();
			positive_coverage=open_positive_coverage.ExtractIni();
*/

//				SELECTION METHOD 1: most general by positive coverage
/*
			{
				FeatureTerm *f=0;
				int *max_c=0,*c;
				bool *pc=0,*max_pc=0;

				open_descriptions.Rewind();
				open_coverage.Rewind();
				open_positive_coverage.Rewind();
				while(open_descriptions.Iterate(f) && open_coverage.Iterate(c) && open_positive_coverage.Iterate(pc)) {
					if (max_c==0 || *c>*max_c) {
						description=f;
						max_c=c;
						max_pc=pc;
					} // if  
				} // while  

//					printf("%i\n",*max_c);

				open_descriptions.DeleteElement(description);
				open_coverage.DeleteElement(max_c);
				open_positive_coverage.DeleteElement(max_pc);
				delete max_c;
				positive_coverage=max_pc;

			} 	
*/

//				SELECTION METHOD 2: most general by subsumption
			{
				FeatureTerm *f=0;
				int *max_c=0,*c;
				bool *pc=0,*max_pc=0;

				description=0;
				open_descriptions.Rewind();
				open_coverage.Rewind();
				open_positive_coverage.Rewind();
				while(open_descriptions.Iterate(f) && open_coverage.Iterate(c) && open_positive_coverage.Iterate(pc)) {
					if (description==0 || f->subsumes(description)) {
						description=f;
						max_c=c;
						max_pc=pc;
					} // if  
				} // while  

//					printf("%i\n",*max_c);

				open_descriptions.DeleteElement(description);
				open_coverage.DeleteElement(max_c);
				open_positive_coverage.DeleteElement(max_pc);
				delete max_c;
				positive_coverage=max_pc;
			} 

			/* This is just an integrity test: */ 
/*
			{
				bool tmp;
				i=0;
				positive.Rewind();
				while(positive.Iterate(problem)) {
					tmp=description->subsumes(problem);
					printf("(%i)%s - (%i)%s\n",positive_coverage[i],(positive_coverage[i] ? "true":"false"),tmp,(tmp ? "true":"false"));
					if ((positive_coverage[i] && !tmp) ||
						(!positive_coverage[i] && tmp)) {
						char *s;
						printf("Integrity failure with:\n");
						s=description->toStringNOOS(domain_model);
						printf("%s\n\n",s);
						delete []s;
					} // if 
					i++;
				} // while  
			}
*/
			
			/* This is another integrity test: */ 
/*
			{
				FeatureTerm *f;

				open_descriptions.Rewind();
				while(open_descriptions.Iterate(f)) {
					if (description->subsumes(f) || f->subsumes(description)) {
						char *s;
						printf("Integrity error!!\n");

						s=f->toStringNOOS(domain_model);
						printf("%s\n",s);
						delete []s;
						s=description->toStringNOOS(domain_model);
						printf("%s\n",s);
						delete []s;
					} // if  
				} // while
			}
*/

/*
			{
				char *s;
				FeatureTerm *f;

				printf("***************************************************\n");
				open_descriptions.Rewind();
				while(open_descriptions.Iterate(f)) {
					s=f->toStringNOOS(domain_model);
					printf("%s\n",s);
					delete []s;
				}  while  			
				s=description->toStringNOOS(domain_model);
				printf("\nConsidering:\n%s\n\n",s);
				delete []s;
			}
*/
			refinements = DSpecializationL2_b(description,&positive,0,o,domain_model);

			while(!refinements->EmptyP()) {
				int positive_covered=0;
//					int negative_covered=0;

				refinement=refinements->ExtractIni();

				valid=false;
				i=0;
				positive.Rewind();
				while(positive.Iterate(problem) && !valid) {
					if (positive_coverage[i] && refinement->subsumes(problem)) valid=true;
					i++;
				} /* while */ 
/*
				if (refinement->subsumes(description)) {
					{
						char *s;
						printf("SPECIALIZATION ERROR!!!!\n");
						printf("Original:\n");
						s=description->toStringNOOS(domain_model);
						printf("%s\n",s);
						delete []s;
						printf("Specialization:\n");
						s=refinement->toStringNOOS(domain_model);
						printf("%s\n",s);
						delete []s;
					}
					valid=false;
				} // if  
*/
				if (valid) {
/*
					{
						char *s;
						s=refinement->toStringNOOS(domain_model);
						printf("Refinement:\n%s\n\n",s);
						delete []s;
					}
*/
					is_solution=true;
					negative.Rewind();
					while(negative.Iterate(problem) && is_solution) {
						if (refinement->subsumes(problem)) is_solution=false;
					} /* while */ 

					if (is_solution) {
						/* Solution found!!!: */ 
						bool *coverage=new bool[positive.Length()];

						i=0;
						positive.Rewind();
						while(positive.Iterate(problem)) {
							if (positive_coverage[i] && refinement->subsumes(problem)) {
								positive_covered++;
								coverage[i]=true;
							} else {
/*
								if (refinement->subsumes(problem)) {
									printf("ERROR 1!!!!\n");
									if (description->subsumes(problem)) printf("Even description also subsumes the example!!\n");
									{
										char *s;
										s=description->toStringNOOS(domain_model);
										printf("Description:\n%s\n",s);
										delete []s;
										s=refinement->toStringNOOS(domain_model);
										printf("Refinement:\n%s\n",s);
										delete []s;
										printf("The problem occurred in positive example %i\n",i);
									}
								} // if  
*/
								coverage[i]=false;
							} /* if */ 
							i++;
						} /* while */ 

						if (new_coverage_p(solution,coverage,positive.Length())) {
							int i;
							FeatureTerm *gr,*f;
							List<FeatureTerm> pos,neg;

							i=0;
							positive.Rewind();
							while(positive.Iterate(f)) {
								if (coverage[i]) pos.Add(f);
											else neg.Add(f);
								i++;
							} /* while */ 
							negative.Rewind();
							while(negative.Iterate(f)) neg.Add(f);

							gr=generalize_pattern(refinement,&pos,&neg,o,domain_model);
							while(!pos.EmptyP()) pos.ExtractIni();
							while(!neg.EmptyP()) neg.ExtractIni();

							delete refinement;
							refinement=gr;

							new_pattern=true;
							m_patterns.Add(refinement);
							m_solutions.Add(new FeatureTerm(solution));
							m_reliability.Add(new float(1));
							m_positive_coverage.Add(coverage);

							printf("rINDUCTION2: new rule found , covers %i positive examples and %i negative examples\n",positive_covered,0);
							show_coverage(coverage,positive.Length());
							{
								char *s1,*s2;
								s1=solution->toStringNOOS(domain_model);
								s2=refinement->toStringNOOS(domain_model);
								printf("rINDUCTION2: rule is for class %s,\n%s\n\n",s1,s2);
								delete []s1;
								delete []s2;
							}					
							fflush(0);

							if (positive_covered==positive.Length()) {
								/* A definitive pattern has been found. No need for more patterns!! */ 
								open_descriptions.Delete();
								open_coverage.Delete();
								open_positive_coverage.Delete();
								refinements->Delete();
							} /* if */ 
						} else {
//								printf("rINDUCTION2: new rule found, but does not have new coverage: ");
//								show_coverage(coverage,positive.Length());
							delete refinement;
							delete []coverage;
							
						} /* if */ 
					} else {
						bool advances=true;

						open_descriptions.Rewind();
						while(open_descriptions.Iterate(d) && advances) {
							if (refinement->subsumes(d)) advances=false;
						} /* while */ 

						if (advances) {
							int count=0;
							bool *coverage=new bool[positive.Length()];

							i=0;
							positive.Rewind();
							while(positive.Iterate(problem)) {
								if (positive_coverage[i] && refinement->subsumes(problem)) {
									count++;
									coverage[i]=true;
								} else {
/*
									if (refinement->subsumes(problem)) {
										printf("ERROR 2!!!!\n");
									} // if  
*/
									coverage[i]=false;
								} /* if */ 
								i++;
							} /* while */ 

							if (new_coverage_p(solution,coverage,positive.Length())) {
								/* Delete all the descriptions more general than "refinement": */ 
/*
								{
									List<FeatureTerm> to_delete;
									List<int> to_delete_i;
									List<bool> to_delete_b;
									int *c;
									bool *pc;

									open_descriptions.Rewind();
									open_coverage.Rewind();
									open_positive_coverage.Rewind();
									while(open_descriptions.Iterate(d) && open_coverage.Iterate(c) && open_positive_coverage.Iterate(pc)) {
										if (d->subsumes(refinement)) {
											bool del=true;
											
											for(i=0;i<positive.Length();i++) {
												if (pc[i] && !coverage[i]) del=false;
											} // for  

											if (del) {
												to_delete.Add(d);
												to_delete_i.Add(c);
												to_delete_b.Add(pc);
											} // if  
										} // if 
									} // while  

//										printf("%i/%i eliminated\n",to_delete.Length(),open_descriptions.Length());

									while(!to_delete.EmptyP()) {
										d=to_delete.ExtractIni();
										open_descriptions.DeleteElement(d);
										delete d;
									} // while 
									while(!to_delete_i.EmptyP()) {
										c=to_delete_i.ExtractIni();
										open_coverage.DeleteElement(c);
										delete c;
									} // while  
									while(!to_delete_b.EmptyP()) {
										pc=to_delete_b.ExtractIni();
										open_positive_coverage.DeleteElement(pc);
										delete pc;
									} // while  
								}
*/

								open_descriptions.Add(refinement);
								open_coverage.Add(new int(count));
								open_positive_coverage.Add(coverage);
							} else {
								delete refinement;
								delete []coverage;
							} /* if */ 
						} else {
							delete refinement;
						} /* if */ 
					} /* if */ 
				} else {
					delete refinement;
				} /* if */ 

			} /* while */ 
			delete []positive_coverage;
			delete refinements;
			delete description;
			
			/* Filter current open descriptions: */ 
			if (new_pattern) {
				List<FeatureTerm> to_delete;
				List<int> to_delete_i;
				List<bool> to_delete_b;
				int *c;
				bool *pc;

				open_descriptions.Rewind();
				open_coverage.Rewind();
				open_positive_coverage.Rewind();
				while(open_descriptions.Iterate(d) && open_coverage.Iterate(c) && open_positive_coverage.Iterate(pc)) {
//						show_coverage(coverage,positive.Length());
					if (!new_coverage_p(solution,pc,positive.Length())) {
						to_delete.Add(d);
						to_delete_i.Add(c);
						to_delete_b.Add(pc);
					} /* if */ 
				} /* while */ 

				printf("%i/%i eliminated\n",to_delete.Length(),open_descriptions.Length());
				fflush(0);

				while(!to_delete.EmptyP()) {
					d=to_delete.ExtractIni();
					open_descriptions.DeleteElement(d);
					delete d;
				} /* while */ 
				while(!to_delete_i.EmptyP()) {
					c=to_delete_i.ExtractIni();
					open_coverage.DeleteElement(c);
					delete c;
				} /* while */ 
				while(!to_delete_b.EmptyP()) {
					pc=to_delete_b.ExtractIni();
					open_positive_coverage.DeleteElement(pc);
					delete pc;
				} /* while */ 

				new_pattern=false;
			} /* if */ 


		}while(!open_descriptions.EmptyP());

	} /* if */ 

	filter_rules(solution,positive.Length(),o,domain_model);

	return true;
} /* rINDUCTIONHypothesis::learn2_single_class */ 





bool rINDUCTIONHypothesis::new_coverage_p(FeatureTerm *solution,bool *coverage,int len)
{
	bool new_coverage=true,*c;
	List<bool> l;
	List<FeatureTerm> l2;
	FeatureTerm *s;
	int i;

	l.Instance(m_positive_coverage);
	l2.Instance(m_solutions);
	l.Rewind();
	l2.Rewind();
	while(l.Iterate(c) && 
		  l2.Iterate(s) && new_coverage) {
		if (*s==*solution) {
			new_coverage=false;
			for(i=0;i<len;i++) {
				if (coverage[i] && !c[i]) new_coverage=true;
			} /* if */ 
		} /* if */ 
	} /* while */ 

	return new_coverage;
} /* rINDUCTIONHypothesis::new_coverage_p */ 


void rINDUCTIONHypothesis::show_coverage(bool *coverage,int len)
{
	int i;
	for(i=0;i<len;i++) {
		if (coverage[i]) printf("1");
				    else printf("0");
	} /* for */ 
	printf("\n");
} /* rINDUCTIONHypothesis::show_coverage */ 





FeatureTerm *rINDUCTIONHypothesis::generalize_pattern(FeatureTerm *pattern,List<FeatureTerm> *positive,List<FeatureTerm> *negative,Ontology *o,FTKBase *domain_model)
{
	List<FeatureTerm> l3;
	List<FeatureTerm> *l;
	FeatureTerm *f,*f2,*d;
	bool end,c1,c2;

	f=new FeatureTerm(pattern);

	do{
		end=true;
		l=DGeneralization(f,o,domain_model);

		l->Rewind();
		while(l->Iterate(f2) && end) {
/*
			{
				char *s;
				s=f2->toStringNOOS(domain_model);
				printf("Considering: \n%s\n",s);
				delete []s;
			}
*/			
			c1=true;
			l3.Instance(*positive);
			l3.Rewind();
			while(l3.Iterate(d) && c1) {
				if (!f2->subsumes(d)) {
					c1=false;
/*
					{
						char *s;
						s=d->toStringNOOS(domain_model);
						printf("Does not subsume: \n%s\n",s);
						delete []s;
					}
*/
				} /* if */ 
			} /* while */ 

			c2=true;
			l3.Instance(*negative);
			l3.Rewind();
			while(l3.Iterate(d) && c2) {
				if (f2->subsumes(d)) c2=false;
			} /* while */ 

			if (c1 && c2) {
//				printf("Ok\n");
				delete f;
				f=new FeatureTerm(f2);
				end=false;
			} else {
//				printf("Fail %s %s\n",(c1 ? "true":"false"),(c2 ? "true":"false"));
			} /* if */ 
		} /* if */ 
		delete l;
	}while(!end);
/*
	{
		char *s;
		s=f->toStringNOOS(domain_model);
		printf("Generalized pattern: \n%s\n",s);
		delete []s;
	}
*/

	return f;
} /* rINDUCTIONHypothesis::generalize_pattern */ 



void rINDUCTIONHypothesis::filter_rules(FeatureTerm *solution,int len,Ontology *o,FTKBase *dm)
{
	List<FeatureTerm> to_delete;
	FeatureTerm *f,*s;
	int k;
	float *ftmp;
	bool *cov1;
	List<FeatureTerm> rules_to_consider;

	printf("Filtering rules... (%i rules)\n",m_patterns.Length());
	fflush(0);


	m_patterns.Rewind();
	m_solutions.Rewind();
	while(m_patterns.Iterate(f) && m_solutions.Iterate(s)) {
		if (*s==*solution) {
			rules_to_consider.Add(f);
		} // if 
	} // while 

	printf("Only considering %i\n",rules_to_consider.Length());
	fflush(0);

	/* Obtain a small subset of rules: */ 
	{
		int i;
		int min_nrules=0,min_cost=0;
		int *min_combination=0;
		int *combination;
		int *pattern_cost;
		int *current_coverage;
		int *pattern_correspondence;

		current_coverage=new int[len];
		combination=new int[rules_to_consider.Length()];
		min_combination=new int[rules_to_consider.Length()];
		pattern_cost=new int[rules_to_consider.Length()];
		pattern_correspondence=new int[rules_to_consider.Length()];	
		for(i=0;i<rules_to_consider.Length();i++) {
			combination[i]=0;
			min_combination[i]=0;
			pattern_correspondence[i]=m_patterns.PositionRef(rules_to_consider[i]);
			{
				List<FeatureTerm> tmp;
				List<int> tmp_l;
				Generalize(rules_to_consider[i],0,&tmp,&tmp_l,o,dm,true);
				pattern_cost[i]=*tmp_l[0];
			}
			printf(".");
			fflush(0);
		} /* for */ 
		printf("\n");
			fflush(0);
		for(i=0;i<len;i++) current_coverage[i]=0;

		/* Pretest to determine whether complete coverage is possible!: */ 
		{
			int j;
			for(j=0;j<rules_to_consider.Length();j++) {
				for(i=0;i<len;i++) {
					if (m_positive_coverage[pattern_correspondence[j]][i]) current_coverage[i]++;
				} /* for */ 
			} /* for */ 
			printf("Total coverage is:\n");
			fflush(0);
			for(i=0;i<len;i++) {
				if (current_coverage[i]==0) printf(".");
				if (current_coverage[i]>0 && current_coverage[i]<10) printf("%i",current_coverage[i]);
				if (current_coverage[i]>=10) printf("+");
			} /* for */ 
			printf("\n");
			fflush(0);
			for(i=0;i<len;i++) current_coverage[i]=0;

		}
		filter_rules_heuristic(rules_to_consider.Length(),len,combination,current_coverage,pattern_cost,pattern_correspondence,&min_nrules,&min_cost,min_combination);

		for(i=0;i<len;i++) current_coverage[i]=0;
		filter_rules_auxiliar(rules_to_consider.Length(),len,0,0,0,combination,current_coverage,pattern_cost,pattern_correspondence,&min_nrules,&min_cost,min_combination);
		

		/* Keep the best combination: */ 
		{
			for(i=0;i<rules_to_consider.Length();i++) {
				if (min_combination[i]==0) {
					to_delete.Add(rules_to_consider[i]);
				} /* if */ 
			} /* for */ 

			while(!to_delete.EmptyP()) {
				f=to_delete.ExtractIni();
				k=m_patterns.PositionRef(f);
				f=m_patterns[k];
				m_patterns.DeletePosition(k);
				delete f;
				f=m_solutions[k];
				m_solutions.DeletePosition(k);
				delete f;
				ftmp=m_reliability[k];
				m_reliability.DeletePosition(k);
				delete ftmp;
				cov1=m_positive_coverage[k];
				m_positive_coverage.DeletePosition(k);
				delete []cov1;
			} /* while */ 
		}  

		delete []pattern_correspondence;
		delete []current_coverage;
		delete []min_combination;
		delete []pattern_cost;
		delete []combination;

		while(!rules_to_consider.EmptyP()) rules_to_consider.ExtractIni();

	}

} /* rINDUCTIONHypothesis::filter_rules */ 



void rINDUCTIONHypothesis::filter_rules_auxiliar(int total_nrules,int nexamples,int current,int nrules,int cost,int *combination,int *current_coverage,int *rule_costs,int *pattern_correspondence,int *min_nrules,int *min_cost,int *min_combination)
{
	int i;
	bool complete=true;

	/* Test current combination */ 
	for(i=0;i<nexamples;i++) if (current_coverage[i]==0) complete=false;

	if (complete) {
		if (*min_nrules==-1 || 
			nrules<*min_nrules ||
			(nrules==*min_nrules && cost<*min_cost)) {
			printf("Combination found with %i rules and cost %i\n",nrules,cost);
			printf("Rules: ");
			for(i=0;i<total_nrules;i++) printf("%c",(combination[i]==1 ? '*':'.'));
			printf("\n");
			printf("Coverage: ");
			for(i=0;i<nexamples;i++) printf("%i",current_coverage[i]);
			printf("\n");
			fflush(0);
			*min_nrules=nrules;
			*min_cost=cost;
			for(i=0;i<total_nrules;i++) min_combination[i]=combination[i];
		} /* if */ 
	} else {
		if (current<total_nrules) {
			if (*min_nrules==0 || 
				nrules<*min_nrules ||
				(nrules==*min_nrules && cost<*min_cost)) {
				for(i=0;i<nexamples;i++) if (m_positive_coverage[pattern_correspondence[current]][i]) current_coverage[i]++;
				combination[current]=1;
				filter_rules_auxiliar(total_nrules,nexamples,current+1,nrules+1,cost+rule_costs[current],combination,current_coverage,rule_costs,pattern_correspondence,min_nrules,min_cost,min_combination);
				for(i=0;i<nexamples;i++) if (m_positive_coverage[pattern_correspondence[current]][i]) current_coverage[i]--;
			} /* if */ 
			combination[current]=0;
			filter_rules_auxiliar(total_nrules,nexamples,current+1,nrules,cost,combination,current_coverage,rule_costs,pattern_correspondence,min_nrules,min_cost,min_combination);
		} /* if */ 
	} /* if */ 
} /* rINDUCTIONHypothesis::filter_rules_auxiliar */ 



void rINDUCTIONHypothesis::filter_rules_heuristic(int total_nrules,int nexamples,int *combination,int *current_coverage,int *rule_costs,int *pattern_correspondence,int *min_nrules,int *min_cost,int *min_combination)
{
	bool complete=false;
	int i,j;
	int selected_rule=-1;
	int covered=0;
	int max_covered=0;

	do{
		complete=false;
		selected_rule=-1;
		covered=0;
		max_covered=0;

		/* Select the rule that more uncovered examples covers: */ 
		for(j=0;j<total_nrules;j++) {
			if (combination[j]==0) {
				covered=0;
				for(i=0;i<nexamples;i++) if (current_coverage[i]==0 && m_positive_coverage[pattern_correspondence[j]][i]) covered++;

				if (covered>max_covered) {
					max_covered=covered;
					selected_rule=j;
				} /* if */ 
			} /* if */ 
		} /* for */ 
		for(i=0;i<nexamples;i++) if (m_positive_coverage[pattern_correspondence[selected_rule]][i]) current_coverage[i]++;
		(*min_nrules)++;
		(*min_cost)+=rule_costs[selected_rule];
		combination[selected_rule]=1;
		min_combination[selected_rule]=1;

		/* Test for completeness: */ 
		complete=true;
		for(i=0;i<nexamples;i++) if (current_coverage[i]==0) complete=false;
	}while(!complete);

	printf("Heuristic combination found with %i rules and cost %i\n",*min_nrules,*min_cost);
	printf("Rules: ");
	for(i=0;i<total_nrules;i++) printf("%c",(min_combination[i]==1 ? '*':'.'));
	printf("\n");
	printf("Coverage: ");
	for(i=0;i<nexamples;i++) printf("%i",current_coverage[i]);
	printf("\n");
	fflush(0);
} /* rINDUCTIONHypothesis::filter_rules_heuristic */ 


